/*
 * @Date: 2024-04-21 09:11:36
 * @LastEditors: 玄绮 shijiahansi@qq.com
 * @LastEditTime: 2024-04-21 15:31:20
 * @FilePath: \BigTalkDataStructure\tools\tree\valtree.c
 */
#include "valtree.h"

#include <stdbool.h>
#include <stdlib.h>
#include <sys/stat.h>

enum {
    BF_RH = -1,
    BF_EH = 0,
    BF_LH = +1
};

/**
 * @brief 对以 P 为根的二叉树作右旋处理
 * @brief 处理之后 p 指向新的树根节点，即旋转之前的左子树的根节点
 * @param p
 */
inline static void R_Rotate(VAL_Tree_t* p) {
    VAL_Tree_t L;
    L = (*p)->lchild;          // L 指向 p 的左子树根节点
    (*p)->lchild = L->rchild;  // L 的右子树挂接为 p 的左子树
    L->rchild = *p;            // p 挂接为 L 的右子树
    *p = L;                    // p 指向新的根节点
}

/**
 * @brief 对以 P 为根的二叉树作左旋处理
 * @brief 处理之后 p 指向新的树根节点，即旋转之前的右子树的根节点
 * @param p
 */
inline static void L_Rotate(VAL_Tree_t* p) {
    VAL_Tree_t R;
    R = (*p)->rchild;          // R 指向 p 的右子树根节点
    (*p)->rchild = R->lchild;  // R 的左子树挂接为 p 的右子树
    R->lchild = *p;            // p 挂接为 R 的左子树
    *p = R;                    // p 指向新的根节点
}

/**
 * @brief 左旋平衡处理
 *
 * @param t
 */
static void left_balance(VAL_Tree_t* t) {
    VAL_Tree_t l, lr;
    l = (*t)->lchild;
    switch (l->bf) {
        case BF_LH:
            (*t)->bf = l->bf = BF_EH;
            R_Rotate(t);
            break;

        case BF_RH:
            lr = l->rchild;
            switch (lr->bf) {
                case BF_LH:
                    (*t)->bf = BF_RH;
                    l->bf = BF_RH;
                    break;

                case BF_EH:
                    (*t)->bf = l->bf = BF_EH;
                    break;

                case BF_RH:
                    (*t)->bf = BF_EH;
                    l->bf = BF_LH;
                    break;
            }
            lr->bf = BF_EH;
            L_Rotate(&(*t)->lchild);
            R_Rotate(t);
            break;
    }
}

/**
 * @brief 二叉树左旋平衡处理
 *
 * @param t
 */
static void right_balance(VAL_Tree_t* t) {
    VAL_Tree_t r, rl;
    r = (*t)->rchild;

    switch (r->bf) {
        case BF_RH:
            (*t)->bf = r->bf = BF_EH;
            L_Rotate(t);
            break;

        case BF_LH:
            rl = r->lchild;
            switch (rl->bf) {
                case BF_RH:
                    (*t)->bf = r->bf = BF_LH;
                    r->bf = BF_EH;
                    break;

                case BF_EH:
                    (*t)->bf = r->bf = BF_EH;
                    break;

                case BF_LH:
                    (*t)->bf = BF_EH;
                    r->bf = BF_RH;
                    break;
            }
            rl->bf = BF_EH;
            R_Rotate(&(*t)->rchild);
            L_Rotate(t);
    }
}

// 平衡二叉树的递归插入操作
static bool insertVAL(VAL_Tree_t* t, VAL_TreeDate_t e, bool* taller) {
    if (!*t) {
        *t = (VAL_Tree_t)malloc(sizeof(VAL_TreeNode_t));
        (*t)->data = e;
        (*t)->lchild = (*t)->rchild = NULL;
        (*t)->bf = BF_EH;
        *taller = true;
    }
    else {
        if (e == (*t)->data) {
            *taller = false;
            return false;
        }
        else if (e < (*t)->data) {
            if (!insertVAL(&(*t)->lchild, e, taller)) {
                return false;
            }

            if (*taller) {
                switch ((*t)->bf) {
                    case BF_LH:
                        left_balance(t);
                        *taller = false;
                        break;

                    case BF_EH:
                        (*t)->bf = BF_LH;
                        *taller = true;
                        break;

                    case BF_RH:
                        (*t)->bf = BF_EH;
                        *taller = false;
                        break;
                }
            }
        }
        else {
            if (!insertVAL(&(*t)->rchild, e, taller)) {
                return false;
            }

            if (*taller) {
                switch ((*t)->bf) {
                    case BF_LH:
                        (*t)->bf = BF_EH;
                        *taller = false;
                        break;

                    case BF_EH:
                        (*t)->bf = BF_RH;
                        *taller = true;
                        break;

                    case BF_RH:
                        right_balance(t);
                        *taller = false;
                        break;
                }
            }
        }
    }
    return true;
}

/**
 * @brief 平衡二叉树的插入
 *
 * @param t
 * @param data
 * @return true
 * @return false
 */
bool valtree_insert(VAL_Tree_t* t, VAL_TreeDate_t data) {
    bool taller = false;
    bool statu = insertVAL(t, data, &taller);

    // if (statu && taller) {
    //     if (data < (*t)->data) {
    //         switch ((*t)->bf) {
    //             case BF_LH:
    //                 left_balance(t);
    //                 break;
    //             case BF_EH:
    //                 (*t)->bf = BF_LH;
    //                 break;
    //             case BF_RH:
    //                 (*t)->bf = BF_EH;
    //                 break;
    //         }
    //     }
    //     else if (data > (*t)->data)  {
    //         switch ((*t)->bf) {
    //             case BF_LH:
    //                 (*t)->bf = BF_EH;
    //                 break;
    //             case BF_EH:
    //                 (*t)->bf = BF_RH;
    //                 break;
    //             case BF_RH:
    //                 right_balance(t);
    //                 break;
    //         }
    //     }
    // }
    return statu;
}